package leetcode.editor.cn.q1_300.q200;
// 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
//
// 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
//
//
//
// 示例 1：
//
//
// 输入：s = "1 + 1"
// 输出：2
//
//
// 示例 2：
//
//
// 输入：s = " 2-1 + 2 "
// 输出：3
//
//
// 示例 3：
//
//
// 输入：s = "(1+(4+5+2)-3)+(6+8)"
// 输出：23
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 3 * 10⁵
// s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
// s 表示一个有效的表达式
// '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
// '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
// 输入中不存在两个连续的操作符
// 每个数字和运行的计算将适合于一个有符号的 32位 整数
//
//
// 👍 907 👎 0

/**
 * 有更好的办法可以用，但是没有写出来，写道递归，果然是 5%
 *
 * 看了答案，是用栈解决的
 */
public class Q224_BasicCalculator {
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int calculate(String s) {
            return process(s);
        }

        private int process(String s) {
            if (s.length() == 1) {
                return Integer.parseInt(s);
            }

            int num = 0;
            char opt = '+';
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == ' ') {
                    continue;
                }
                if (c >= '0' && c <= '9') {
                    sb.append(c);
                } else {
                    if (sb.length() > 0) {
                        int cur = Integer.parseInt(sb.toString());
                        sb.delete(0, sb.length());
                        num = opt == '+' ? num + cur : num - cur;
                    }
                    if (c == '(') {
                        String str = getSubStr(s, i);
                        num = opt == '+' ? num + process(str) : num - process(str);
                        i += str.length() + 1;
                    } else {
                        opt = c;
                    }
                }
            }
            if (sb.length() > 0) {
                int cur = Integer.parseInt(sb.toString());
                num = opt == '+' ? num + cur : num - cur;
            }
            return num;
        }

        private String getSubStr(String s, int i) {
            int num = 0;
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (c == '(') {
                    num++;
                } else if (c == ')') {
                    num--;
                    if (num == 0) {
                        sb.deleteCharAt(0);
                        return sb.toString();
                    }
                }
                sb.append(c);
            }
            return null;
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new Q224_BasicCalculator().new Solution();
        // TO TEST
        System.out.println(solution.calculate("((198))"));
        System.out.println(solution.calculate("- (((1)))"));
        System.out.println(solution.calculate("- (3 + (4 + 5))"));
        System.out.println(solution.calculate(" 1+ 1"));
        System.out.println(solution.calculate(" 2-1 + 2"));
        System.out.println(solution.calculate("(1+(4+5+2)-3)+(6+8)"));
    }
}